package mo.tags.stack;

import mo.common.ListNode;

import java.util.Stack;

public class L445 {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        ListNode tmp = l1;
        while (tmp != null) {
            s1.push(tmp.val);
            tmp = tmp.next;
        }
        tmp = l2;
        while (tmp != null) {
            s2.push(tmp.val);
            tmp = tmp.next;
        }
        ListNode tail = null;
        int add = 0;
        while (!s1.isEmpty() && !s2.isEmpty()) {
            Integer n1 = s1.pop();
            Integer n2 = s2.pop();
            int cur = (n1 + n2 + add) % 10;
            if (tail == null) {
                tail = new ListNode(cur);
            } else {
                ListNode node = new ListNode(cur);
                node.next = tail;
                tail = node;
            }
            add = (n1 + n2 + add) / 10;
        }
        while (!s1.isEmpty() || !s2.isEmpty()) {
            Stack<Integer> s = s1.isEmpty() ? s2 : s1;
            Integer val = s.pop();
            int cur = (val + add) % 10;
            add = (val + add) / 10;
            ListNode node = new ListNode(cur);
            node.next = tail;
            tail = node;
        }
        if (add != 0) {
            ListNode node = new ListNode(add);
            node.next = tail;
            tail = node;
        }
        return tail;
    }

}
